package com.muchfish.algorithm.linkedlist;

import com.muchfish.algorithm.linkedlist.pojo.ListNode;

/**
 * <a href="https://leetcode.cn/problems/swap-nodes-in-pairs/description/">题目：24. 两两交换链表中的节点</a>
 * <br>
 * 题目描述：<br>
 * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
 * <br>
 * <img src="https://assets.leetcode.com/uploads/2020/10/03/swap_ex1.jpg">
 * 解题思路： <br>
 * 1. 递归（推荐，好理解）<br>
 * 1.1 获取新的上一节点：当前节点的下一节点为新的上一节点<br>
 * 1.2 为当前节点设置下一节点：当前节点的下一节点为新的（递归）下一节点<br>
 * 1.3 为新的上一节点设置下一节点：新的上一节点的下一节点为当前节点<br>
 * 1.3.1 步骤3不能在步骤2后，否则会造成循环引用<br>
 * 2. 迭代<br>
 * 2.1 创建虚拟头节点，指向头节点<br>
 * 2.2 创建临时节点，指向虚拟头节点<br>
 * 2.3 创建当前节点，指向临时节点的下一节点<br>
 * 2.4 创建下一节点，指向当前节点的下一节点<br>
 * 2.5 创建下一节点的下一节点，指向当前节点的下一节点<br>
 * 2.6 返回虚拟头节点的下一节点<br>
 * <br>
 */
public class LinkedList5 {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1, new ListNode(2, new ListNode(4)));

    }
    public static ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }

    /**
     * 递归（推荐，好理解）
     * @param head
     * @return
     */
    public static ListNode swapPairs1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //1.获取新的上一节点：当前节点的下一节点为新的上一节点
        ListNode newHead = head.next;
        //2.为当前节点设置下一节点：当前节点的下一节点为新的（递归）下一节点
        head.next = swapPairs(newHead.next);
        //3.为新的上一节点设置下一节点：新的上一节点的下一节点为当前节点
        //步骤3不能在步骤2后，否则会造成循环引用
        newHead.next = head;
        return newHead;
    }
}
